#!/usr/bin/python

from collections import defaultdict
from math import log
from itertools import ifilter
from copy import deepcopy


class inner_node(object):

    def __init__(self, attribute, children):
        self._attr, self._children = attribute, children

    def predict(self, record):
        aval = record[self._attr]
        return self._children[aval].predict(record)


class leaf_node(object):

    def __init__(self, value):
        self.value = value

    def predict(self, record):
        return self.value


def entropy(records):
    counter, total = defaultdict(int), 0
    for point, value in records:
        counter[value] += 1
        total += 1
    total = float(total)

    summ = 0
    for v in counter.itervalues():
        p = float(v) / float(total)
        summ += p * log(p)

    return -summ


def compute_attr_gain(records, no):
    values, total = defaultdict(int), 0
    for record, klass in records:
        values[record[no]] += 1
        total += 1

    e = 0
    for value, num in values.iteritems():
        def f(x):
            return x[0][no] == value
        ev = entropy(ifilter(f, records))
        e += ev * float(num) / float(total)
    return e


def compute_gain_ratio(records, no):
    values, total = defaultdict(int), 0
    for record, klass in records:
        values[record[no]] += 1
        total += 1

    ig, iv = 0, 0
    for value, number in values.iteritems():
        p = float(number) / float(total)
        ig += p * entropy(ifilter(lambda x : x[0][no] == value, records))
        iv += p * log(p)
    iv = - iv

    return ig / iv


def find_split_attribute(records, attrs):
    min_gain, min_attr = 1, None
    for attribute in attrs:
        #again = compute_attr_gain(records, attribute)
        again = compute_gain_ratio(records, attribute)
        if again < min_gain:
            min_attr = attribute
            min_gain = again
    return min_attr


def get_common(values_list):
    r = defaultdict(int)
    for value in values_list:
        r[value] += 1
    return max(r.iteritems(), key=itemgetter(1))[0]


def build_inner_node(records, attribute, attrs):
    child_records = defaultdict(list)
    for record in records:
        child_records[record[0][attribute]].append(record)

    child_nodes = {}
    for aval, arecs in child_records.iteritems():
        child_nodes[aval] = build_node(arecs, deepcopy(attrs))

    return inner_node(attribute, child_nodes)


def check_uniqueness(records):
    do_one, only_value = True, records[0][1]
    for _, value in records[1:]:
        if value != only_value:
            do_one = False
            break
    if do_one:
        return True, only_value
    else:
        return False, None


def build_node(records, attrs):
    if len(attrs) == 0:
        return leaf_node(get_common(v for p, v in records))

    else:
        # can we create only one node?
        is_unique, value = check_uniqueness(records)
        if is_unique:
            return leaf_node(value)
        else:
            attribute = find_split_attribute(records, attrs)
            attrs_copy = deepcopy(attrs)
            attrs_copy.remove(attribute)
            return build_inner_node(records, attribute, attrs_copy)

def gini(records, attrs):
    '''Creates decision tree with Gini index.'''
